package com.ankie.algorithm;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;

/**
 * @ClassName ZuHeZongHe2
 * @Author ankie
 * @Date 2020/6/16
 * @Description // TODO
 */
public class ZuHeZongHe2 {

//    public static List<List<Integer>> combinationSum2(int[] candidates, int target) {
//        List<List<Integer>> result = new ArrayList<>();
//        // 判断形参
//        if (candidates == null || candidates.length == 0) {
//            return result;
//        }
//        // 对当前的数组进行排序，方便后面选取路径
//        Arrays.sort(candidates);
//        // 选择栈的目的是为了方便压入弹出
//        backTracking(candidates, 0, target, new Stack<>(), result);
//        return result;
//    }
//
//    private static void backTracking(int[] candidates, int start, int target, Stack<Integer> path, List<List<Integer>> result) {
//        // 作为递归的返回条件
//        if (target == 0) {
//            List<Integer> list = new ArrayList<>(path);
//            result.add(list);
//            return;
//        }
//        int len = candidates.length;
//        // 第一层主循环开始
//        for (int i = start; i < len; i++) {
//            // 1. 结束循环条件
//            if (target < candidates[i]) {
//                break;
//            }
//            while (i > start && i < len && candidates[i-1] == candidates[i]) {
//                i++;
//            }
//            // 2. i在增加后，判断当前的i 是否已经到头了
//            if (i >= len) {
//                break;
//            }
//            path.push(candidates[i]);
//            backTracking(candidates, i + 1, target - candidates[i], path, result);
//            path.pop();
//        }
//    }

    public static void main(String[] args) {
//        // 参考排序好的数组: {1, 1, 2, 5，6, 7, 10}
//        int[] candidates = {10, 1, 2, 7, 6, 1, 5};
//        int target = 8;
////        List<List<Integer>> result = combinationSum2(candidates, target);
//        for (List<Integer> integers : result) {
//            System.out.println(Arrays.toString(integers.toArray()));
//        }
    }
}

